/*
 * @lc app=leetcode.cn id=148 lang=cpp
 *
 * [148] 排序链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
  ListNode* sortList(ListNode* head)
  {
    if (head == nullptr)
      return nullptr;
    vector<ListNode*> nodes;
    for (; head; head = head->next)
      nodes.push_back(head);
    sort(nodes.begin(), nodes.end(), [](ListNode* l, ListNode* r) -> bool {
      return l->val < r->val;
    });
    for (int i = 0; i < nodes.size() - 1; ++i)
      nodes[i]->next = nodes[i + 1];
    nodes.back()->next = nullptr;
    return nodes[0];
  }
};
// @lc code=end
